package math;

import java.util.Random;

/**
 * O(n^log3), but in practical maybe slower than O(n^2) naive algorithm.
 * 
 * So don't use this template !!!
 * 
 * @author yinzichen
 * 
 */
public class PolynomialMultiplication {

	/**
	 * @param a
	 *            a0*x^0+a1*x^1+...+a(n-1)*x^(n-1)
	 * @param b
	 *            b0*x^0+b1*x^1+...+b(n-1)*x^(n-1)
	 * @param n
	 * @return
	 */
	public long[] multiply(int[] a, int[] b, int n) {
		assert (a.length == n && b.length == n);
		return multiply(a, b, 0, n - 1);
	}

	long[] multiply(int[] a, int[] b, int l, int r) {
		long[] res = new long[r - l + r - l + 1];
		if (l == r) {
			res[0] += a[l] * b[l];
			return res;
		}
		int m = l + r >> 1;
		long[] t1 = multiply(a, b, l, m);
		long[] t2 = multiply(a, b, m + 1, r);
		int[] na = new int[m - l + 1];
		int[] nb = new int[m - l + 1];
		for (int i = l; i <= m; ++i) {
			na[i - l] += a[i];
			nb[i - l] += b[i];
		}
		for (int i = m + 1; i <= r; ++i) {
			na[i - m - 1] += a[i];
			nb[i - m - 1] += b[i];
		}
		long[] t3 = multiply(na, nb, 0, m - l);
		for (int i = 0; i < t1.length; ++i) {
			res[i] += t1[i];
			res[i + m - l + 1] -= t1[i];
		}
		for (int i = 0; i < t2.length; ++i) {
			res[i + m + m - l - l + 2] += t2[i];
			res[i + m - l + 1] -= t2[i];
		}
		for (int i = 0; i < t3.length; ++i) {
			res[i + m - l + 1] += t3[i];
		}
		return res;
	}

	String toBigInt(long[] coef) {
		StringBuilder sb = new StringBuilder();
		long carry = 0;
		for (int i = 0; i < coef.length; ++i) {
			sb.append((char) ((coef[i] + carry) % 10 + '0'));
			carry = (coef[i] + carry) / 10;
		}
		while (carry > 0) {
			sb.append(carry % 10);
			carry /= 10;
		}
		while (sb.length() > 1 && sb.charAt(sb.length() - 1) == '0') {
			sb.deleteCharAt(sb.length() - 1);
		}
		return sb.reverse().toString();
	}

	public String bigIntMulti(String p, String q) {
		int n = Math.max(p.length(), q.length());
		int[] a = new int[n];
		int[] b = new int[n];
		for (int i = 0; i < p.length(); ++i) {
			a[p.length() - i - 1] = p.charAt(i) - '0';
		}
		for (int i = 0; i < q.length(); ++i) {
			b[q.length() - i - 1] = q.charAt(i) - '0';
		}
		return toBigInt(multiply(a, b, n));
	}

	public static void main(String[] args) {
		PolynomialMultiplication a = new PolynomialMultiplication();
		long[] res = a.multiply(new int[] { 1, 2, 3, 4 }, new int[] { 4, 3, 2,
				1 }, 4);
		for (long i : res) {
			System.out.print(i + " ");
		}
		System.out.println("\n" + a.toBigInt(res));
		System.out.println("\n" + 1234 * 4321);
		System.out.println("\n" + a.bigIntMulti("9", "99"));
		System.out.println("\n" + a.bigIntMulti("0", "0"));

		int n = 50000;
		StringBuilder sb = new StringBuilder(n);
		Random ran = new Random(1);
		sb.append('1');
		for (int i = 0; i < n; ++i) {
			sb.append((char) (ran.nextInt(10) + '0'));
		}
		long time = System.currentTimeMillis();
		// System.out.println(sb.toString());
		for (int i = 0; i < 1; ++i)
			a.bigIntMulti(sb.toString(), sb.toString());
		System.out.println(System.currentTimeMillis() - time);
	}

}
